Birthday Paradox

Like many things which are named a paradox in mathematics, the birthday paradox is not a paradox at all, but rather a probability problem which has a solution often considered unintuitive.

As is common with this problem, we make the simplifications that the probability of an individual having a given birthday is as likely as any other birthday, and that there are exactly \(365\) days every year.

We choose to identify each date with an element in the set \(\mathbb{Z}/365\mathbb{Z}\), and hence an outcome for the birthdays of all \(n\) people with an element in \((\mathbb{Z}/365\mathbb{Z})^n\).

We know that there are \(|(\mathbb{Z}/365\mathbb{Z})^n| = 365^n\) total outcomes of equal likelihood.

Now, to count the number of outcomes in which no two people share the same birthday, we are counting the number of ways of selecting \(n\) elements from \(\mathbb{Z}/365\mathbb{Z}\) without repetition where order is important.

This is exactly \({}^{365}P_n = \frac{365!}{(365 - n)!}\).

Hence, given all outcomes are of equal likelihood, the probability of an event in which no two people share a common birthday out of \(n\) people is:

Hence the probability that any two people have the same birthday out of \(n\) people is the complementary event of the above, and hence has probability:

The smallest value of \(n\) for this expression to exceed \(\frac{1}{2}\) is \(23\).